class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


import collections


# class Solution(object):
#     def closestKValues(self, root, target, k):
#         """
#         :type root: TreeNode
#         :type target: float
#         :type k: int
#         :rtype: List[int]
#         """
#         stack = [root]
#         out = collections.deque()
#         while stack:
#             node = stack[-1]
#             if node.left:
#                 stack.append(node.left)
#             else:
#                 while stack and not stack[-1].right:
#                     node = stack.pop()
#                     out.append(node.val)
#                 if stack:
#                     node = stack.pop()
#                     out.append(node.val)
#                     stack.append(node.right)
#         return_out = list(out)[: k]
#         for i in range(k, len(out)):
#             if abs(target - return_out[0]) > abs(target - out[i]):
#                 del return_out[0]
#                 return_out.append(out[i])
#             else:
#                 break
#         return return_out

import collections
class Solution(object):
    def closestKValues(self, root, target, k):
        """
        :type root: TreeNode
        :type target: float
        :type k: int
        :rtype: List[int]
        """
        out = collections.deque([root.val])
        out_num = 1
        if root.right:
            right_stack = collections.deque([root.right])
        else:
            right_stack = collections.deque()
        if root.left:
            left_stack = collections.deque([root.left])
        else:
            left_stack = collections.deque()
        if right_stack:
            node = right_stack[-1]
            while node.left:
                right_stack.append(node.left)
                node = node.left
        if left_stack:
            node = left_stack[-1]
            while node.right:
                left_stack.append(node.right)
                node = node.right
        while right_stack and out_num < k:
            node = right_stack.pop()
            out.append(node.val)
            out_num += 1
            if node.right:
                node = node.right
                right_stack.append(node)
                while node.left:
                    right_stack.append(node.left)
                    node = node.left
        while left_stack and out_num < k:
            node = left_stack.pop()
            out.appendleft(node.val)
            out_num += 1
            if node.left:
                node = node.left
                left_stack.append(node)
                while node.right:
                    left_stack.append(node.right)
                    node = node.right
        while True:
            if not left_stack:
                if not right_stack:
                    return list(out)
                else:
                    if target <= out[0]:
                        return list(out)
                    else:
                        node = right_stack.pop()
                        if abs(node.val - target) < abs(out[0] - target):
                            out.popleft()
                            out.append(node.val)
                            if node.right:
                                node = node.right
                                right_stack.append(node)
                                while node.left:
                                    right_stack.append(node.left)
                                    node = node.left
                        else:
                            return list(out)
            else:
                if not right_stack:
                    if target >= out[-1]:
                        return list(out)
                    else:
                        node = left_stack.pop()
                        if abs(node.val - target) < abs(out[-1] - target):
                            out.pop()
                            out.appendleft(node.val)
                            if node.left:
                                node = node.left
                                left_stack.append(node)
                                while node.right:
                                    left_stack.append(node.right)
                                    node = node.right
                        else:
                            return list(out)
                else:
                    if target >= out[-1]:
                        node = right_stack.pop()
                        if abs(node.val - target) < abs(out[0] - target):
                            out.popleft()
                            out.append(node.val)
                            if node.right:
                                node = node.right
                                right_stack.append(node)
                                while node.left:
                                    right_stack.append(node.left)
                                    node = node.left
                        else:
                            return list(out)
                    else:
                        if target <= out[0]:
                            node = left_stack.pop()
                            if abs(node.val - target) < abs(out[-1] - target):
                                out.pop()
                                out.appendleft(node.val)
                                if node.left:
                                    node = node.left
                                    left_stack.append(node)
                                    while node.right:
                                        left_stack.append(node.right)
                                        node = node.right
                            else:
                                return list(out)
                        else:
                            node = right_stack.pop()
                            if abs(node.val - target) < abs(out[0] - target):
                                out.popleft()
                                out.append(node.val)
                                if node.right:
                                    node = node.right
                                    right_stack.append(node)
                                    while node.left:
                                        right_stack.append(node.left)
                                        node = node.left
                                left_stack = collections.deque()
                            else:
                                node = left_stack.pop()
                                if abs(node.val - target) < abs(out[-1] - target):
                                    out.pop()
                                    out.appendleft(node.val)
                                    if node.left:
                                        node = node.left
                                        left_stack.append(node)
                                        while node.right:
                                            left_stack.append(node.right)
                                            node = node.right
                                    right_stack = collections.deque()
                                else:
                                    return list(out)